package com.camus.datastructureandalgorithm.algorithm.sort;

import java.util.Arrays;

/**
 * @author jie.deng
 * 选择排序
 */
public class SelectSortArray implements SortArray {

    @Override
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }
        // 分为已排序区间和未排序区间
        // 每次从未排序区间选择最小的元素，将其与未排序区的第一个元素交换位置，并加入到已排序区。
        // 第i轮，已排序区间为i个元素。从i到len-1选择最小值，与nums[i]交换位置。
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            int min = nums[i];
            int minIdx = i;
            for (int j = i + 1; j < length; j++) {
                if (nums[j] < min) {
                    min = nums[j];
                    minIdx = j;
                }
            }
            if (minIdx != i) {
                nums[i] = nums[i] ^ nums[minIdx];
                nums[minIdx] = nums[i] ^ nums[minIdx];
                nums[i] = nums[i] ^ nums[minIdx];
            }
        }

        return nums;
    }

}
